무방향 그래프

Undirected Graph

두 정점을 연결하는 간선의 방향이 없는 그래프
정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현
정점이 n개인 무방향 그래프에서 최대의 간선 수: n(n-1)/2개

최대 간선 수

정점 n개 가운데 서로 다른 두 정점을 고르는 경우의 수가 곧 놓을 수 있는 간선의 수다. 무방향 그래프에서는 (Vi, Vj) 와 (Vj, Vi) 가 같은 간선이므로 nC2 = n(n-1)/2 개가 최대이고, 이때 모든 정점이 서로 이어진 완전 그래프가 된다. 예: 정점 4개 → 6개, 5개 → 10개.

그래프	정점 n개일 때 간선 수
무방향 그래프의 최대(완전 그래프)	n(n-1)/2
방향 그래프의 최대	n(n-1) — <Vi, Vj> 와 <Vj, Vi> 를 다른 간선으로 센다
연결 그래프의 최소(신장 트리, 트리)	n-1

자기 자신으로 가는 간선(자기 루프)과 같은 두 정점 사이의 중복 간선은 세지 않는 단순 그래프 기준이다.

같이 보기